package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2022-07-08 14:43
 */
public class 题库_0210_课程表II {

  static
  class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
      int[] answer = new int[numCourses];
      int index = 0;
      Set<Integer> already = new HashSet<>();
      Map<Integer, List<Integer>> map = new HashMap<>();
      for (int[] prerequisite : prerequisites) {
        map.putIfAbsent(prerequisite[0], new ArrayList<>());
        map.get(prerequisite[0]).add(prerequisite[1]);
      }

      for (int i = 0; i < numCourses; ++i) {
        if (!map.containsKey(i)) {
          already.add(i);
          answer[index++] = i;
        }
      }

      boolean study;
      do {
        study = false;
        for (int i = 0; i < numCourses; ++i) {
          if (!already.contains(i) && already.containsAll(map.get(i))) {
            already.add(i);
            answer[index++] = i;
            study = true;
          }
        }
      } while (index < numCourses && study);

      return index == numCourses ? answer : new int[0];
    }
  }

}
